package unionFind

// DFS解法
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	count := 0
	// 对于联通的区域，通过dfs深度优先遍历，对值为'1'的节点进行遍历，每次遍历到一个节点，就将该节点值修改为'0'，防止dfs重复遍历相同节点
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				// 每次遇到为'1'的节点，通过dfs将与该节点联通的所有节点都变为'0',count自增1，表示遍历到的岛屿数+1
				count++
				dfs(&grid, i, j)
			}
		}
	}
	return count
}

// 先判断坐标是否符合条件，然后上下左右递归(优先选择这种递归方式)
func dfs(grid *[][]byte, x, y int) {
	nr, nc := len(*grid), len((*grid)[0])
	if x < 0 || y < 0 || x >= nr || y >= nc || (*grid)[x][y] == '0' {
		return
	}
	if (*grid)[x][y] == '1' {
		(*grid)[x][y] = '0'
	}

	dfs(grid, x-1, y)
	dfs(grid, x+1, y)
	dfs(grid, x, y-1)
	dfs(grid, x, y+1)
}

// 通过遍历上下左右四个节点的坐标，然后对符合条件的坐标进行dfs递归
type Node struct {
	X int
	Y int
}

func dfs1(grid *[][]byte, x, y int) {
	if (*grid)[x][y] == '1' {
		(*grid)[x][y] = '0'
	}
	m, n := len(*grid), len((*grid)[0])
	for _, node := range []Node{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}} {
		if node.X >= 0 && node.Y >= 0 && node.X < m && node.Y < n && (*grid)[node.X][node.Y] == '1' {
			dfs1(grid, node.X, node.Y)
		}
	}
}

// BFS解法一
func numIslands1(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	count := 0
	// 每次从队列左边弹出一个元素x，然后判断x的上下左右节点是否符合条件，将符合条件的节点从队列右边压入，然后将节点的值置为'0'，防止重复遍历
	queue := make([]int, 0)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				count++
				queue = append(queue, i*n+j)
				grid[i][j] = '0'
				for len(queue) != 0 {
					node := queue[0]
					// 注意，这里必须写成queue = queue[1:] 而不能是 queue := queue[1:]
					// 因为前者是对同一个底层数组进行操作，而后者是创建了一个新的切片，不会删除原切片的第一个元素，所以或导致无限循环
					queue = queue[1:]
					x, y := node/n, node%n
					if x-1 >= 0 && grid[x-1][y] == '1' {
						queue = append(queue, (x-1)*n+y)
						grid[x-1][y] = '0'
					}
					if x+1 < m && grid[x+1][y] == '1' {
						queue = append(queue, (x+1)*n+y)
						grid[x+1][y] = '0'
					}
					if y-1 >= 0 && grid[x][y-1] == '1' {
						queue = append(queue, x*n+y-1)
						grid[x][y-1] = '0'
					}
					if y+1 < n && grid[x][y+1] == '1' {
						queue = append(queue, x*n+y+1)
						grid[x][y+1] = '0'
					}
				}
			}
		}
	}
	return count
}

// BFS解法二
func numIslands2(grid [][]byte) int {
	// x对应m，y对应n
	m, n := len(grid), len(grid[0])
	count := 0
	queue := make([]Node, 0)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				count++
				grid[i][j] = '0'
				queue = append(queue, Node{i, j})
				for len(queue) != 0 {
					node := queue[0]
					x, y := node.X, node.Y
					queue := queue[1:]
					for _, k := range []Node{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}} {
						if k.X >= 0 && k.Y >= 0 && k.X < m && k.Y < n && grid[k.X][k.Y] == '1' {
							queue = append(queue, k)
							grid[k.X][k.Y] = '0'
						}
					}
				}
			}
		}
	}
	return count
}

// 并查集
func numIslands3(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	uf := new(UnionFind3)
	uf.init(grid)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				// 四方合并和两方合并需要注意的事项
				/*
				假设有矩阵
				1 1 1 0
				1 1 0 0
				0 0 0 0

				如果是四个方向上合并，则(0,0)位置的会和(0,1) (1,0)合并，合并后，第二次遍历到(0,1)节点，如果在第一次遍历时将(0,0)改为'0'，
				则第二次遍历到(0,1)节点时，进行四方合并，左边的（0，0）因为已经被修改为'0'，所以左边这个方向的就不会再合并了;
				但是，如果没有grid[i][j]='0'这一步也是可以的，只是到(0,1)节点处进行四方合并时会对左边节点也调用一次合并函数，其结果是一样的

				由于在节点(m,n)位置需要进行四个方向的合并，而遍历到(m+1,n)节点时又需要遍历四个方向，(m,n)位置会与右边的(m+1,n)合并一次；
				到（m+1,n）位置又会与(m,n)位置合并一次，所以合并两次其实是重复了，只需要合并一次即可，同理上下方向也只需要合并一次即可;
				这里选择只合并上左两个方向，假设（m,n）位置合并了左边和上面的，然后到了(m+1,n)位置，此时合并左方向即(m,n)节点时，如果(m,n)的
				节点值在上一步被修改为了'0',那么这一次就不会再进行合并了，也就是说本来(m+1,n)应该与(m,n)合并，结果不合并了；
				所以再使用双方合并时，千万不能修改节点值,即grid[i][j]='0'是不允许的（这会导致下一个节点双方合并时不会合并左边的节点）
				 */
				//grid[i][j] = '0'
				//if i-1 >= 0 && grid[i-1][j] == '1' {
				//	uf.Union(i*n+j, (i-1)*n+j)
				//}
				//if j-1 >= 0 && grid[i][j-1] == '1' {
				//	uf.Union(i*n+j, i*n+j-1)
				//}
				//if i+1 < m && grid[i+1][j] == '1' {
				//	uf.Union(i*n+j, (i+1)*n+j)
				//}
				//if j+1 < n && grid[i][j+1] == '1' {
				//	uf.Union(i*n+j, i*n+j+1)
				//}
				if i-1 >= 0 && grid[i-1][j] == '1' {
					uf.Union(i*n+j, (i-1)*n+j)
				}
				if j-1 >= 0 && grid[i][j-1] == '1' {
					uf.Union(i*n+j, i*n+j-1)
				}
			}
		}
	}
	return uf.GetCount()
}

type UnionFind3 struct {
	// 记录节点x所在集合的代表节点
	Parent []int
	// 记录集合的秩
	Rank []int
	// 计算不同集合的数量
	Count int
}

func (u *UnionFind3) init(grid [][]byte) {
	m, n := len(grid), len(grid[0])
	u.Parent = make([]int, m*n)
	u.Rank = make([]int, m*n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				u.Parent[i*n+j] = i*n + j
				// 先统计所有为'1'的节点的数量，之后每次合并一个元素到集合，则Count减一，最后Count即代表所有节点值为'1'的不同的集合数
				u.Count++
			} else {
				u.Parent[i*n+j] = -1
			}
		}
	}
}

// 查找节点x的根节点
func (u *UnionFind3) Find(x int) int {
	if x != u.Parent[x] {
		// 将x的父节点设置为x所在集合的根节点(缩短路径)
		u.Parent[x] = u.Find(u.Parent[x])
	}
	return u.Parent[x]
}

// 按秩合并
func (u *UnionFind3) Union(i, j int) {
	rootX, rootY := u.Find(i), u.Find(j)
	if rootX != rootY {
		// 将rootX设置为秩较小的根节点，将rootY设置为秩较大的根节点
		if u.Rank[rootX] > u.Rank[rootY] {
			rootX, rootY = rootY, rootX
		}
		// 将秩较小的集合合并到秩较大的集合
		u.Parent[rootX] = rootY
		if u.Rank[rootX] == u.Rank[rootY] {
			u.Rank[rootY]++
		}
		// 每次合并一个元素，就将Count减一（因为之前Count统计了所有值为'1'的元素）
		u.Count--
	}
}

// 返回Count值
func (u *UnionFind3) GetCount() int {
	return u.Count
}
